#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max_cost_recur(vector<int> &w, vector<int> &c, int n, int m)
{
	if(n == 0){
		return 0;
	}

	int max_cost = max_cost_recur(w, c, n - 1, m);
	if(w[n] <= m){
		max_cost = max(max_cost, max_cost_recur(w, c, n - 1, m - w[n]) + c[n]);
	}

	return max_cost;
}

int max_cost_recur(vector<int> &w, vector<int> &c, int n, int m, vector<vector<int>> &recd)
{
	if(n == 0){
		return 0;
	}

	if(recd[n][m] != -1){
		return recd[n][m];
	}

	int max_cost = max_cost_recur(w, c, n - 1, m, recd);
	if(w[n] <= m){
		max_cost = max(max_cost, max_cost_recur(w, c, n - 1, m - w[n], recd) + c[n]);
	}

	return recd[n][m] = max_cost;
}

int max_cost_dp(vector<int> &w, vector<int> &c, int n, int m)
{
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = dp[i - 1][j];
			if(j >= w[i]){
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + c[i]);
			}
		}
	}
	return dp[n][m];
}

int max_cost_dp_sp(vector<int> &w, vector<int> &c, int n, int m)
{
	vector<int> dp(m + 1, 0);
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= w[i]; j--){
			dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
		}
	}
	return dp[m];
}

int main()
{
	int n, m;
	cin >> m >> n;
	vector<vector<int>> gh(n + 1, vector<int>(m + 1, 0));
	vector<int> w(n + 1, 0), c(w);
	for(int i = 1; i <= n; i++){
		cin>>w[i]>>c[i];
	}

	vector<vector<int>> recd(n + 1, vector<int>(m + 1, -1));
	cout<<max_cost_dp_sp(w, c, n, m)<<endl;

	return 0;
	
}